(1) Field of the Invention
The present invention relates to an information processing apparatus such as a microprocessor, and especially relates to an improved technique of branch prediction.
(2) Description of the Prior Art
For an information processing apparatus such as a microprocessor which uses a pipeline structure, a branch prediction is a method used to suppress the disorder in the pipeline which occurs due to branches in the control flow when executing branch instructions. To perform branch prediction with high accuracy, it is necessary to predict whether a conditional branch (referred to as "a branch" hereafter) is performed for each branch instruction (hereafter, whether a branch is performed or not performed is referred to as "taken" and "not taken"). To do so, a branch prediction table, which is a collection of branch prediction information corresponding to each branch instruction in the programs, can be provided.
When the branch prediction table is stored in an internal memory of the information processing apparatus, it results in an increase in the size of the hardware. For this reason, a branch prediction method which minimizes the required size of the hardware of the information processing apparatus has been proposed (See an information processing apparatus disclosed in Japanese Laid-Open Patent Application No. 63-75934, for example). This method does not store the branch prediction information permanently in the internal memory of the information processing apparatus, but has the branch prediction information provided in the branch instructions themselves.
FIG. 1 shows a branch instruction format of this conventional information processing apparatus. As shown in FIG. 1, 1 bit of branch prediction information 40b is provided in a branch instruction 40 and, when decoding the branch instruction 40, the conventional information processing apparatus fetches a next instruction which is to be executed in accordance with the branch prediction information 40b. After the execution of the branch instruction 40, the conventional information processing apparatus compares the execution result with the branch prediction information 40b, and, when the prediction is incorrect, updates the branch prediction information 40b of the branch instruction 40 stored in the memory. By doing so, this information processing apparatus does not need to store the branch prediction table in the internal memory.
Although the required hardware size of the conventional information processing apparatus is reduced, it has a drawback in that the penalties resulting from the failure of the branch prediction are frequently incurred because of the low accuracy of the branch prediction.
In other words, the conventional information processing apparatus prefetches a next instruction in accordance with the 1-bit branch prediction information showing the execution result of the preceding instruction. When, for example, the conditions that a branch is taken are only satisfied during alternate execution, all predictions will be incorrect. Therefore, the prefetched instruction has to be invalidated every time such branch prediction is executed, which prevents the information processing apparatus from processing at high speed.